package AlgorithmStudy.study;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;


/**
 * 移除字符串中重复元素，并不改变相对位置，按字典最小序输出
 * 主要：将非重复元素放到map  来查看是否是最后一次出现
 */
public class RemoveDuplicateLetter {

    public String removeDuplicateLetters(String s) {

        // 栈
        Stack<Character> stack = new Stack<>();

        // this lets us keep track of what's in our solution in O(1) time
        // set
        HashSet<Character> seen = new HashSet<>();

        // this will let us know if there are any more instances of s[i] left in s
        // map 将字符串中字母存入 去重  map<字母,下标>
        HashMap<Character, Integer> last_occurrence = new HashMap<>();
        for(int i = 0; i < s.length(); i++) last_occurrence.put(s.charAt(i), i);
        // last_occurrence   a 2   b 6   c 7   d 4

        // 遍历字符串  c b a c d c b c
        // c b c d c b c a
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            // we can only try to add c if it's not already in our solution
            // this is to maintain only one of each character
            // set集合中没有该字符
            if (!seen.contains(c)){
                // if the last letter in our solution:
                //     1. exists
                //     2. is greater than c so removing it will make the string smaller
                //     3. it's not the last occurrence
                // we remove it from the solution to keep the solution optimal
                // 栈不为空；字符小于栈顶元素；栈顶字符不是最后一次出现 ----> set中移除  stack中移除
                while(!stack.isEmpty() && c < stack.peek() && last_occurrence.get(stack.peek()) > i){
                    seen.remove(stack.pop());
                }
                seen.add(c);
                stack.push(c);
            }
        }
        StringBuilder sb = new StringBuilder(stack.size());
        for (Character c : stack) sb.append(c.charValue());
        return sb.toString();
    }

    public static void main(String[] args) {
        RemoveDuplicateLetter removeDuplicateLetter = new RemoveDuplicateLetter();
        String str = removeDuplicateLetter.removeDuplicateLetters("cbacdcbc");  //acdb
//        String str = removeDuplicateLetter.removeDuplicateLetters("cbacdcc");  //bacd
//        String str = removeDuplicateLetter.removeDuplicateLetters("cbcdcbca");  // bcda

//        String a = "没人";
//        String b = "比我";
//        String c = "更懂";
//        String d = "java";
//        String s = a + b + c + d;

        System.out.printf(str);
    }

}
